package org.hw.algorithm.sortUtil;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class SortFactory {


    /*交换数组中的left和right位置的值*/
    public static void swap(int[] array, int left, int right) {
        int temp = array[left];
        array[left] = array[right];
        array[right] = temp;
    }

    /************************************************冒泡排序*****************************************/
    /**
     * 冒泡排序：
     * 第一次遍历交换：将最大的数放到数组最后，随后一位有序最大。
     * 第二次遍历交换：将次大的数放到数组倒数第二位，则从倒数第二位到末尾有序，且递增。
     * 依次类推，总共进行 arr.length-1 次遍历交换，直到数组整体有序
     * 每次遍历交换的元素需要排除已经放置到数组末尾有序的元素，则需要遍历交换的元素的范围是：0 ~ [(arr.length-1)-当前遍历次数]
     */
    //写法一
    public static void bubbleSort1(int[] arr) {
        int len = arr.length;
        for (int i = 0; i < len - 1; i++) {
            for (int j = 0; j < (len - 1) - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                }
            }
        }
    }

    //写法二
    public static void bubbleSort2(int[] nums) {
        // 外循环：未排序区间为[0, i]
        for (int i = nums.length - 1; i > 0; i--) {
            // 内循环：将未排序区间[0, i] 中的最大元素交换至该区间的最右端
            for (int j = 0; j < i; j++) {
                if (nums[j] > nums[j + 1]) {
                    // 交换nums[j] 与nums[j + 1]
                    swap(nums, j, j + 1);
                }
            }
        }
    }

    /**
     * 优化的冒泡排序:
     * 在当前遍历的过程中如果没有发生元素交换，那么说明整个数组已经有序了，后续不需要再遍历交换，直接结束排序
     */
    public static void bubbleSortOptimize(int[] nums) {
        // 外循环：未排序区间为[0, i]
        for (int i = nums.length - 1; i > 0; i--) {
            boolean flag = false; // 初始化标志位
            // 内循环：将未排序区间[0, i] 中的最大元素交换至该区间的最右端
            for (int j = 0; j < i; j++) {
                if (nums[j] > nums[j + 1]) {
                    // 交换nums[j] 与nums[j + 1]
                    swap(nums, j, j + 1);
                    flag = true; // 记录交换元素
                }
            }
            if (!flag)
                break; // 此轮“冒泡”未交换任何元素，直接跳出
        }
    }

    /************************************************选择排序*****************************************/
    /**
     * 选择排序
     * 1. 从数组的第一个元素开始，逐个与后面的数进行比较交换
     * 2. 然后再从第二个元素开始与后面的元素进行比较交换
     * 3. 依次类推直到数组有序
     */
    public static void selectSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    swap(arr, i, j);
                }
            }
        }
    }


    /************************************************插入排序*****************************************/

    /**
     * 写法一（交换法）：
     * i 序号往后遍历数组
     * j 序号从 当前i 的位置开始往前进行比对
     * 最终将 当前i 位置的数放到前部分已排序数列的合适位置
     */
    public static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0; j--) {
                if (arr[j] < arr[j - 1]) {
                    swap(arr, j, j - 1);
                } else {
                    break;
                }
            }
        }
    }

    /*写法二（移位法）：*/
    public static void insertSort2(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int key = array[i];
            int j = i - 1;
            // 将大于key的元素向后移动
            while (j >= 0 && array[j] > key) {
                array[j + 1] = array[j];
                j--;
            }
            // 找到key的插入位置并插入
            array[j + 1] = key;
        }
    }

    /************************************************希尔排序：改进版本的插入排序*****************************************/
    /**
     * gap 步长，将整个数组根据步长分成若干组，对每组进行 直接插入排序
     * 教程链接：https://blog.csdn.net/qq_56127002/article/details/126414650
     * 写法一（交换法）：
     */
    public static void shellSort(int[] arr) {
        // 设置初始增量 gap，通常取数组长度的一半，然后每次减半
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            // 从每一个gap开始的元素，执行插入排序
            for (int i = gap; i < arr.length; i++) {
                // 将arr[i]插入到arr[i-gap], arr[i-2*gap]...等已排序的子序列中
                for (int j = i; j >= gap; j -= gap) {
                    if (arr[j - gap] > arr[j]) {
                        swap(arr, j - gap, j);
                    }
                }
            }
        }
    }

    /*写法二（移位法）：*/
    public static void shellSort2(int[] arr) {
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                //插入排序，将arr[i]插入到arr[i-gap], arr[i-2*gap]...等已排序的子序列中
                int key = arr[i];
                int j = i;
                while (j >= gap && arr[j - gap] > key) {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                arr[j] = key;
            }
        }
    }

    /************************************************分步骤的快速排序*****************************************/

    /*单次排序：确定基准值进行排序并返回基准值最终位置*/
    public static int partition(int[] array, int left, int right) {
        int pivot = left;
        while (left < right) {
            while (array[right] >= array[pivot] && left < right) {
                right--;
            }
            while (array[left] <= array[pivot] && left < right) {
                left++;
            }
            swap(array, left, right);
        }
        swap(array, left, pivot);
        return left;
    }

    /*快速排序：递归排序*/
    public static void quickSortP(int[] array, int left, int right) {
        if (left >= right) {
            return;
        }
        int index = partition(array, left, right);
        quickSortP(array, left, index - 1);
        quickSortP(array, index + 1, right);
    }

    /************************************************合并的快速排序*****************************************/

    /*合并的快速排序：就是将比基准值pivot大的元素放到pivot右边，反之放到pivot左边，依次对全部数组元素进行运算，直至整体有序*/
    public static void quickSort(int[] arr, int left, int right) {
//        当left<right 意味着数组元素大于一个
        if (left < right) {
//            数组第一个数作为基数
            int pivot = arr[left];
//            从左到右进行查找指示当前左位置
            int i = left;
//            从右到左进行查找指示当前右位置
            int j = right;
            while (i < j) {
//                从右往左找比基准值pivot小的第一个数替换arr[i]
                while (i < j && pivot <= arr[j]) j--;
                arr[i] = arr[j];
//                从左往右找到比基准值pivot大的第一个数替换arr[j]
                while (i < j && pivot >= arr[i]) i++;
                arr[j] = arr[i];
            }
//          第一轮排序完成，pivot放入数组中，pivot左边的元素都比pivot小，右边的都比pivot大
            arr[i] = pivot;
//          对其他部分，使用递归进行排序
            quickSort(arr, left, i - 1);
            quickSort(arr, i + 1, right);
        }
    }

    /************************************************归并排序*****************************************/
    // 归并
    public static void mergeSort(int array[], int first, int last, int temp[]) {
        if (first < last) {
            int mid = (first + last) / 2;
            mergeSort(array, first, mid, temp); // 递归归并左边元素
            mergeSort(array, mid + 1, last, temp); // 递归归并右边元素
            mergeArray(array, first, mid, last, temp); // 再将上面两个有序数列合并
        }
    }

    /**
     * 合并两个有序数列
     * array[first]~array[mid]为第一组
     * array[mid+1]~array[last]为第二组
     * temp[]为存放两组比较结果的临时数组
     */
    private static void mergeArray(int array[], int first, int mid, int last, int temp[]) {
        int i = first, j = mid + 1; // i为第一组的起点, j为第二组的起点
        int k = 0; // k用于指向temp数组当前放到哪个位置
        while (i <= mid && j <= last) { // 将两个有序序列循环比较, 按照从小到大依次填入数组temp，其中必然有一组先于另一组结束
            if (array[i] <= array[j])
                temp[k++] = array[i++];
            else
                temp[k++] = array[j++];
        }
        while (i <= mid) { // 如果比较完毕, 第一组还有数剩下, 则全部填入temp
            temp[k++] = array[i++];
        }
        while (j <= last) {// 如果比较完毕, 第二组还有数剩下, 则全部填入temp
            temp[k++] = array[j++];
        }
        for (i = 0; i < k; i++) {// 将排好序的数填回到array数组的对应位置
            array[first + i] = temp[i];
        }
    }

    /************************************************桶排序*****************************************/

    public static List<Integer> bucketSort(int[] arr) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            min = Math.min(min, arr[i]);
            max = Math.max(max, arr[i]);
        }
//         创建桶
        int bucketNum = (max - min) / arr.length + 1;//桶的数量
        List<List<Integer>> bucketArry = new ArrayList<>(bucketNum);//初始化桶
        for (int i = 0; i < bucketNum; i++) {
            bucketArry.add(new ArrayList<Integer>());
        }

//         将元素放入桶中
        for (int i = 0; i < arr.length; i++) {
            int num = (arr[i] - min) / (arr.length);
            bucketArry.get(num).add(arr[i]);
        }

//         桶中元素排序
        for (int i = 0; i < bucketArry.size(); i++) {
            Collections.sort(bucketArry.get(i));
        }
//         取出桶中元素合并
        List<Integer> arrlist = new ArrayList<>();
        for (List<Integer> ls : bucketArry) {
            arrlist.addAll(ls);
        }
        return arrlist;
    }

    /************************************************基数排序*****************************************/
    /**
     * 最低位优先法(LSD)：
     * 就是对每个元素的每一位进行比较，放入对应序号的桶中，然后再按照桶序号收集起来，直至整个数组有序。没有高位的数用0代替，放入0号桶中。
     * 1、分解：
     * 获取每个元素的个位，放入个位数值对应序号的桶中，例如123，个位是3，则将123放入序号为3的桶中
     * 2、收集：
     * 按照桶的编号从小到大的顺序依次收集桶内的元素，桶内如果有多个元素，也是按照下标从小到大的顺序拿出（先进先出）。
     * 例如有0、1桶中都有元素，则先拿0号桶，如果0号桶中有 10,50,30三个数，拿出来的顺序也是10,50,30
     * 3、迭代：
     * 重复 1,2步骤，直至最大元素的最高位也经过了处理。也就是循环 [最大元素的位数] 次。
     * <p>
     * 基数排序的时间复杂度为 O(nk)，其中 n 是待排序元素的数量，k 是最大数的位数（在十进制下，通常是最大的数有多少位）。
     * 这是因为每一趟分配和收集操作的时间复杂度都为 O(n)，而总共有 k 趟这样的操作。
     * 相比于大多数比较型排序算法（如快速排序、归并排序等），基数排序在处理大规模整数并且数据范围不特别大的情况下，具有较高的效率优势。
     */
    public static void radixSort(int[] arr, int maxVal) {
        // 获取最大值的位数，以便确定循环次数
        int maxDigits = String.valueOf(maxVal).length();
        // 创建10个桶（假设基数是10）
        List<Integer>[] buckets = new ArrayList[10];
        // 初始化桶
        for (int i = 0; i < buckets.length; i++) {
            buckets[i] = new ArrayList<>();
        }

        // 对每一位进行处理
        for (int digit = 0; digit < maxDigits; digit++) {
            // 将元素分配到相应的桶里
            for (int num : arr) {
                int value = getDigit(num, 10, digit); // 获取当前位的数值
                buckets[value].add(num);
            }
            // 清空原数组并从桶中重新收集元素
            int index = 0;
            for (List<Integer> bucket : buckets) {
                for (int num : bucket) {
                    arr[index++] = num;
                }
                bucket.clear(); // 清空桶，避免重复添加
            }
        }
    }

    /**
     * 辅助方法，获取数字的某一位数值
     *
     * @param num   原始值
     * @param radix 基数（十进制通常是10）
     * @param exp   指数，从0开始，任何数的0次方都是1
     */
    private static int getDigit(int num, int radix, int exp) {
        return (num / (int) Math.pow(10, exp)) % radix;
    }
/************************************************计数排序*****************************************/
    /**
     * 计数数组中，数组下标包含原数组的值，数组的值代表原数组的值出现的次数
     * 核心思想是将原数组的值映射到计数数组的下标上，将原数组在计数数组当前下标的个数作为计数数组的当前下标值
     * 适合用于 整数的排序，且数据范围较小的情况
     */
    public static void countSort(int[] arr) {
        int max = arr[0];
        int min = arr[0];
        /*查找最大和最小值*/
        for (int i = 0; i < arr.length; i++) {
            if (max < arr[i]) max = arr[i];
            if (min > arr[i]) min = arr[i];
        }

        /*创建计数数组*/
        int[] countArr = new int[max - min + 1];
        for (int i = 0; i < arr.length; i++) {
            countArr[arr[i] - min]++;
        }

        /*根据计数数组取出排序数列*/
        int begin = 0;
        for (int i = 0; i < countArr.length; i++) {
            // 如果当前下标中原数组中数据出现了 0 次，也就是原数组中没有出现当前下标对应的数字，则退出当前循环
            if (countArr[i] == 0) continue;
            for (int j = 0; j < countArr[i]; j++) {
                arr[begin++] = i + min;
            }
        }
    }
}
